(●˙꒳˙●)
嗨，我是wec，今天是DAY 15。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

給定一棵二叉樹，找出兩個節點p和q的最近公共祖先節點（Lowest Common Ancestor）。
1.所有節點的值都是唯一的。
2.p、q為不同節點且均存在於給定的二元樹中。

🔎 解題思路＆程式碼

1️⃣ 遞迴

第1步： 如果當前節點是nil，返回nil。如果當前節點是p或q，則返回當前節點。
第2步： 分別對左右子樹進行遞迴。
第3步： 根據左右子樹的返回結果來判斷：
1.如果左子樹返回nil，則最近的公共祖先在右子樹。
2.如果右子樹返回nil，則最近的公共祖先在左子樹。
3.如果左右子樹都不為nil，則當前節點就是最近的公共祖先。
程式碼：

def lowest_common_ancestor(root, p, q)
  return nil if root.nil?
  return root if root == p || root == q

  left = lowest_common_ancestor(root.left, p, q)
  right = lowest_common_ancestor(root.right, p, q)

  return root if left && right
  left || right
end

🔎 總結

時間複雜度

遞迴法： 時間複雜度為O(n)，n為節點數量。
➡️ 公共祖先的概念可以應用在很多地方，例如文件系統之類(要查共同父層的時候)，理解樹的結構及遞迴遍歷的特性是解決問題的關鍵，這樣就不用一直去紀錄每個節點的父節點，提高效率!ヽ(・∀・)ﾉ

那麽，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃起司夾心餅。
明天要說：Ruby精選刷題！Medium路跑D-8(>∀･)⌒☆